As it is known by the man skilled in the art, during operation in a random access network packet losses can be either due to channel errors or due to collisions.
One means here by “collision losses” packet losses that occur when two or more packets arrive simultaneously (or “collide”) at a receiver node.
Moreover one means here by “channel error losses” packet losses that do not involve simultaneous packet transmissions and that are due to the (wireless) channel (or link) between a transmitter node and a receiver node. It is recalled that the (wireless) channel behavior depends notably on node locations and/or transmit power and/or received signal strength and/or (wireless) hardware implementation and/or environmental factors.
Packet loss rate during network operation can be measured by means of groups of probe packets transmitted between nodes during pre-specified probing time windows. In this case, the packet loss rate is the fraction of probe packets that have been lost during a pre-specified probing time window. Unfortunately it is much more difficult to separate (or compute) the two components of the measured packet loss rate, i.e. the channel loss rate and the collision loss rate, during the operation of a random access network, whereas it is of interest for the two following reasons.
Firstly, this separation enables efficient joint operation of random access MAC protocols and data rate adaptation mechanisms. It is recalled that random access protocols and data rate adaptation mechanisms aim at addressing different causes of packet loss. Random access MAC protocols aim to address losses due to collisions by carrier sensing and contention window adaptation, while data rate adaptation mechanisms aim to improve channel quality on an individual link by adapting the modulation data rate. Both random access MAC protocols and data rate adaptation mechanisms trade off throughput efficiency for packet loss avoidance, but they both require knowledge of the cause of packet loss for correct operation. Unfortunately, this information is not provided by the physical (PHY) layer specifications of existing (wireless) standards. So, all random access MAC protocols assume that a packet loss is due to collisions and therefore increase the contention window size (in case of CSMA/CA) or the backoff probability (in case of ALOHA), and all data rate adaptation mechanisms assume that a packet loss is due to poor channel quality and therefore decrease the modulation data rate to lower the bit error probability by increasing the transmit power available to each bit. Therefore, unless these mechanisms can correctly ascertain the causes of packet losses, they may take unnecessary or erroneous actions that result in inefficient operation.
Secondly, this separation enables accurate capacity estimation, traffic optimizations and admission control in random access networks. In contrast to networks using scheduled access MAC protocols, such as Time Division Multiple Access (TDMA), it is well known by the man skilled in the art that it is hard to model and optimize networks using random access MAC protocols. Traffic optimizations require measurement of a traffic-independent network state (link capacity) to optimally allocate traffic to available resources. Accurately estimating this traffic-independent network state calls for measuring link capacities in the absence of collisions, as these collisions may only arise once traffic has been allocated in the network. Separation of collision losses (traffic-dependent) and channel error losses (traffic independent) is, therefore, crucial for properly sizing link capacities so as to be able to allocate traffic to optimize the performance of random access networks.
Solutions which have been proposed to separate channel losses from collision losses can be approximately shared in two classes: a two-phase class and a continuous class. In a two-phase class solution the network periodically suspends operation to measure channel loss rates, while in a continuous class solution the network operation is never suspended.
More precisely, a two-phase class solution is based on the division of the time of network operation in two phases: a measurement phase and a normal network operation phase. During the measurement phase, normal network operation is suspended and the nodes must execute a sequential transmission technique to broadcast probe packets sequentially in a scheduled manner. Since only one node transmits at a time, this solution can measure the channel loss rates of all communication links in the network during this probing window, using O(N) measurements, where N is the number of nodes in the network. Then, the collision rate for this probing window is extracted from the measured packet loss rate of the subsequent normal network operation phase.
Unfortunately these two-phases class solutions seem impractical and not applicable to an operational network. Indeed, they impose an extended network downtime just for network measurements. In order to collect sufficient statistics, each node needs to transmit for tens of seconds during the measurement phase, as mentioned in the document of Jitendra Padhye et al., “Estimation of Link Interference in Static Multi-hop Wireless Networks”, Proceedings of Internet Measurement Conference, Berkeley, Calif., October 2005, or in the document of Lili Qiu et al., “A general model of wireless interference”, Proceedings of International Conference on Mobile Computing and Networking, Montréal, Canada, September 2007, or in the document of Anand Kashyap et al., “A measurement-based approach to modeling link capacity in 802.11-based wireless networks”, Proceedings of International Conference on Mobile Computing and Networking, Montreal, Canada, September 2007, or else in the document of Charles Reis et al., “Measurement-based models of delivery and interference in static wireless networks”, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, Pisa, Italy, September 2006. Thus, each measurement phase can result in network downtime of several minutes even for small networks of 20-30 nodes.
Moreover, the implementation of the sequential technique in an operational network requires a signaling protocol to coordinate the nodes so that they could be able to switch between the two phases. This signaling protocol is itself a source of overhead and is difficult to implement in general network environments (multi-hop or distributed, for instance).
The continuous class comprises per-packet solutions that attempt to detect the cause of packet loss for each transmitted packet, and passive monitoring techniques where additional monitoring devices “sniff” received packets and send packet timing information to a centralized point which is in charge of estimating the loss rates using global information.
A first solution of the continuous class is described in the document of S. Rayanchu et al., “Diagnosing Wireless Packet Losses in 802.11: Separating Collision from Weak Signal”, IEEE INFOCOM 2006, Barcelona, Spain. This first solution attempts to diagnose the cause of loss on a per-packet basis in 802.11 WLANs, that are single-hop networks consisting of clients connected to an access point (AP). For each packet transmitted by a client and received in error at an access point, the latter acknowledges with a copy of this erroneous packet. Then, the client uses statistical techniques to determine whether the packet was corrupted due to collisions or channel losses. This technique can be used to estimate channel loss rate and collision loss rate by counting the fractions of corrupted packets due to channel errors during a pre-specified time window.
This first solution has several drawbacks. Firstly, it introduces overhead due to the additional acknowledgment packets (and this overhead is increased when communication links are lossy). Secondly, the acknowledgement packets are assumed to be loss-free, but in practice they are subject to both channel losses and collision losses. Thirdly, channel loss rates and collision loss rates can only be estimated for received corrupted packets at the access point, not for packets that were transmitted but not received at this access point. Fourthly, it is specific to the client/access point WLAN environment and exploits a special type of feedback from the access point that provides information on bit errors and symbol errors within a packet.
A second solution of the continuous class is described in the document of K. Whitehouse et al., “Exploiting the capture effect for collision detection and recovery”, EmNetS-11, 2005. This second solution attempts to detect two types of collisions in the presence of capture in a sensor network: stronger-first and stronger-last where the packet with the stronger power comes first and last, respectively. In a stronger-first collision the receiver node detects a collision by finding a new extra termination symbol, while in a stronger-last collision the receiver node detects a collision by finding a new preamble during the reception of another packet.
This second solution has several drawbacks. Firstly, it can be only applied to restricted collision scenarios for successful detection (the transmissions which result in a collision should have enough differences in transmission start time and receiving power). Secondly, a stronger-last detection requires modifications on the transmitter node side (a new extra termination symbol). Thirdly, it requires low-level access to communication parameters which is not provided by most existing standards.
A third solution of the continuous class is described in the document of J. Yun et al., “Collision detection based on RF energy duration in IEEE 802.11 wireless LAN”, Comsware, 2006, New Delhi, India. It aims at detecting collision in 802.11 WLANs by measuring the RF energy and its changes during such an event. The main assumption is that the RF energy duration of a collision is greater than the RF energy duration of individual transmissions. The access point of a basic service set (BSS) measures RF energy duration on a channel and broadcasts this result to its clients. Then, the clients detect collisions by checking the duration against the duration of their previous transmission schedules.
This third solution has several drawbacks. Firstly, it is specific to WLAN scenarios and requires low-level access and MAC layer modifications which are not provided by the 802.11 standard. Secondly, it may introduce significant overhead to communicate the RF energy information from an access point back to its clients.
A fourth solution of the continuous class is described in the document of S. Wong et al., “Robust rate adaptation for 802.11 wireless networks”, ACM Mobicom, 2006, Los Angeles, Calif., and in the document of J. Kim et al., “CARA: Collision-aware rate adaptation for IEEE 802.11 WLANs”, IEEE INFOCOM 2006, Barcelona, Spain. This fourth solution is based on the use of RTS/CTS MAC layer control messages that precede data transmissions to detect collisions and perform intelligent data rate adaptation in 802.11 WLANs. Failure of the RTS/CTS packets is attributed to collision because these packets are small and sent at the lowest modulation data rate, and failure of data packet following a successful RTS/CTS is attributed to channel loss. To reduce overhead, the RTS/CTS mechanism is enabled adaptively only when collision is detected.
This fourth solution has several drawbacks. Firstly, it is specific to 802.11 WLANs and data rate adaptation mechanisms. Secondly, accurate computation of collision and channel error rates requires the 802.11 RTS/CTS mechanism to be always enabled. However in practice RTS/CTS is typically not enabled due to the high overhead, especially at the higher modulation data rates. Thirdly, it requires modifications of the 802.11 MAC protocol which are not supported by the 802.11 standard.
A fifth solution of the continuous class is described in the document of Y. Cheng et al., “Jigsaw: solving the puzzle of enterprise 802.11 analysis”, ACM SIGCOMM, 2006, Pisa, Italy, and in the document of R. Mahajan et al., “Analyzing the MAC-level behavior of wireless networks in the wild”, ACM SIGCOMM, 2006, Pisa, Italy. This fifth solution is based on passive monitoring techniques consisting in computing packet overlaps using monitor nodes and global network knowledge. Monitor nodes are dedicated hardware devices that “sniff” all packets received around the normal nodes and report them to a central server. The central server is in charge of computing all timings based on a global reference and then of determining which packets overlapped in time.
This fifth solution has several drawbacks. Firstly, it introduces an implementation complexity and a communication overhead for communicating all the information to the central server. Secondly, it requires a global up-to-date network knowledge at the central server to perform an accurate estimation. Even with such global knowledge it is not straightforward to infer collision loss or channel loss, because packet overlaps do not always result in collision losses, due to physical capture which is difficult to model in general. Thirdly, the predictive power of a passive monitoring technique heavily depends on how densely the monitor nodes are deployed, because when the density increases the probability that a monitor node is close to any given communication link increases.